Busca e Ordenação: A Pedra Fundamental para Grandes Volumes de Dados

Busca e ordenação não são apenas o início dos cursos de algoritmos, mas sim a lógica fundamental da ciência da computação no processamento de dados. O valor dos dados depende da eficiência com que podem ser recuperados e organizados. Esta seção revela o cerne da avaliação de algoritmos por meio da busca linear mais básica,busca linear— ou seja, como localizar um objetivo por comparação linear em diferentes formas de dados.

1. Lógica e Custo

Busca Linear:从列表中的第一个元素开始，沿着默认的顺序逐个查看，直到找到目标元素或者查完列表。其时间复杂度是 $O(n)$.

2. Comparação de Desempenho: Desordenado vs Ordenado

Emlistas desordenadas中（见下表），无论成功与否，平均比对次数通常与 $n$ 成正比。而在listas ordenadas中，利用数据的排列规则可以实现“提前终止”：当遇到比目标值更大的元素时即可断定目标不存在。虽然这未改变 $O(n)$ 的本质，但优化了失败查找的平均效率。